public class Solution {
    /* https://leetcode-cn.com/problems/surrounded-regions/
     * 被围绕的区域
     * 找到边界上为"O"的位置，搜索 其上下左右与其相连的"O" 讲"O"置为任意字符 "P"
     * 最后将 "P" 除"P"外的所有位置置为 "X",将 "P" 置为 "O"
     *
     * */
    public void DFS(char[][] board, int row, int col, int newR, int newC) {
        if (newR >= row || newR < 0 || newC >= col || newC < 0) {
            return;
        }
        if (board[newR][newC] != 'O') {
            return;
        }
        board[newR][newC] = 'P';
        for (int[] next : nextP) {
            int newX = newR + next[0];
            int newY = newC + next[1];
            DFS(board, row, col, newX, newY);
        }
    }

    public void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                DFS(board, row, col, 0, j);
            }
        }
        for (int j = 0; j < col; j++) {
            if (board[row - 1][j] == 'O') {
                DFS(board, row, col, row - 1, j);
            }
        }
        for (int i = 1; i < row - 1; i++) {
            if (board[i][0] == 'O') {
                DFS(board, row, col, i, 0);
            }
        }
        for (int i = 1; i < row - 1; i++) {
            if (board[i][col - 1] == 'O') {
                DFS(board, row, col, i, col - 1);
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'P') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    //BFS
    public void solve2(char[][] board) {
        Queue<Pair> queue = new LinkedList<>();
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < col; i++) {
            if(board[0][i] == 'O'){
                queue.offer(new Pair(0,i));
            }
        }
        for (int i = 0; i < col; i++) {
            if(board[row-1][i] == 'O'){
                queue.offer(new Pair(row-1,i));
            }
        }
        for (int i = 1; i < row; i++) {
            if(board[i][0] == 'O'){
                queue.offer(new Pair(i,0));
            }
        }
        for (int i = 1; i < row; i++) {
            if(board[i][col-1] == 'O'){
                queue.offer(new Pair(i,col-1));
            }
        }
        while(!queue.isEmpty()){
            Pair pair = queue.poll();
            board[pair.x][pair.y] = 'P';
            for (int[] next : nextP) {
                int nx = pair.x + next[0];
                int ny = pair.y + next[1];
                if(nx >= row || nx < 0 || ny >= col || ny < 0){
                    continue;
                }
                if(board[nx][ny] == 'O'){
                    queue.offer(new Pair(nx,ny));
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j] != 'P'){
                    board[i][j] = 'X';
                }else{
                    board[i][j] = 'O';
                }
            }
        }
    }
}